package org.tokaf.algorithm;

import java.util.ArrayList;
import java.util.Collections;

import org.tokaf.MyTopKCompareValues;
import org.tokaf.TopKElement;
import org.tokaf.bestcolumnfinder.BestColumnFinder;
import org.tokaf.datasearcher.DataSearcher;
import org.tokaf.rater.Rater;

/**
 * <p>Implementation of Threshold algorithm.
 * Major concept is threshold value, which is computed of last values seen by every datasearcher.
 * When rating of object exceeds rating of threshold, no further objects can be in k best objects.
 * </p>
 * <p>Copyright (c) 2006</p>
 * @author Alan Eckhardt
 * @version 1.0
 */
public class ThresholdAlgorithm extends Algorithm {

	ArrayList<TopKElement> sortedK;

	double multiplicative = 1;

	double additive = 0;

	TopKElement threshold = null;

	MyTopKCompareValues comp = new MyTopKCompareValues();

	/**
	 * run
	 * 
	 * @return ArrayList of top k objects
	 */
	public ArrayList run() {
		long startTime = System.nanoTime();
		ArrayList a;
		if (data.length > 0) {
			a = runThresholdAlgorithm();
		} else
			a = new ArrayList();
		runTime = System.nanoTime() - startTime;
		return a;
	}

	/**
	 * @return Threshold value.
	 */
	public TopKElement getThreshold() {
		return threshold;
	}

	/**
	 * Gets the multiplicative coefficient
	 * @return the vaule of multiplicative coefficient
	 */
	double getMultiplicative() {
		return multiplicative;
	}

	/**
	 * Sets the multiplicative coefficient
	 * 
	 * @param multiplicative
	 *            double
	 * @return the new vaule of multiplicative coefficient
	 */
	double setMultiplicative(double multiplicative) {
		this.multiplicative = multiplicative;
		return this.multiplicative;
	}

	/**
	 * Gets the additive coefficient
	 * @return the vaule of additive coefficient
	 */
	double getAdditive() {
		return additive;
	}

	/**
	 * Sets the additive coefficient
	 * 
	 * @param additive
	 *            double
	 * @return the new vaule of additive coefficient
	 */
	double setAdditive(double additive) {
		this.additive = additive;
		return this.additive;
	}

	/**
	 * Check if the algorithm ends. If all object in topKlist are better than threshold, algorithm ends.
	 * 
	 * @param threshold
	 *            TopKElement
	 * @return whether the algorithm is about to end.
	 */
	boolean testTopK(TopKElement threshold) {
		//If all object in topKlist are better than threshold, algorithm ends.
		/*for (int i = 0; i < sortedK.size(); i++)
		 if ((((TopKElement) sortedK.get(i)).rating + additive)
		 * multiplicative < (threshold.rating))
		 return false;

		 return true;*/
		if (sortedK.size() < K)
			return false;
		if ((sortedK.get(K - 1).rating + additive)
				* multiplicative < threshold.rating)
			return false;
		return true;
	}

	void insertElement(TopKElement newEl) {

		int length = Math.min(K, sortedK.size());

		int pos = Collections.binarySearch(sortedK, newEl, comp);

		if (pos < 0 && pos >= -(length + 1)) {
			sortedK.remove(newEl);
			sortedK.add(-pos - 1, newEl);
		} else if (pos >= 0 && pos <= (length)) {
			sortedK.remove(newEl);
			sortedK.add(pos, newEl);
		}
		// Should be only one more (size==K)
		// But one never knows
		while (sortedK.size() > K)
			sortedK.remove(K);

		/*
		 if(sortedK.size() < K){	
		 for(int i=0;(i<=K&&i<sortedK.size());i++){   
		 // New element has higher rating, we add new element to this position
		 if(newEl.rating>((TopKElement)sortedK.get(i)).rating){
		 sortedK.add(i,newEl);	
		 return;
		 }
		 }	
		 sortedK.add(newEl);
		 return;
		 }
		 for(int i=0;(i<=K&&i<sortedK.size());i++){   
		 // New element has higher rating, we add new element to this position
		 if(newEl.rating>((TopKElement)sortedK.get(i)).rating){
		 sortedK.add(i,newEl);	
		 break;
		 }
		 }
		 // Should be only one more (size==K)
		 // But one never knows
		 while(sortedK.size()>K)
		 sortedK.remove(K);*/
	}

	/**
	 * Rates new elemnt in the column i.
	 * 
	 * 
	 * @param threshold
	 *            TopKElement
	 * @param  i
	 *            int
	 */
	private void rate(TopKElement threshold, int i) {

		long startTime = System.nanoTime();
		Object subject = data[i].getField(0);
		Object object = data[i].getField(2);
		dataTime = dataTime + System.nanoTime() - startTime;

		startTime = System.nanoTime();
		// Adds actual rating to threshold
		//rater.AddRating(threshold, predicate.toString(), object);
		threshold.setRating(i, object, data[i]);
		ratingTime = ratingTime + System.nanoTime() - startTime;

		startTime = System.nanoTime();
		TopKElement newSubject = new TopKElement(subject.toString(), -1,
				data.length);
		// Finds if we have seen this entity before.
		TopKElement temp = findEntity(newSubject);
		searchTime = searchTime + System.nanoTime() - startTime;

		if (temp == null) {
			topKlist.put(newSubject.name, newSubject);
			for (int j = 0; j < data.length; j++) {
				newSubject.setPosition(j, data[i].getPosistion());
				newSubject.setFound(j, step);

			}

			startTime = System.nanoTime();
			// In other datasearchers, we find all values
			for (int j = 0; j < data.length; j++) {
				//predicate = data[j].findObject(subject, 0, 1);
				object = data[j].findObject(subject, 0, 2);
				if (/*predicate == null ||*/object == null)
					continue;
				//rater.AddRating(newSubject, predicate.toString(), object);
				newSubject.setRating(j, object, data[i]);
				step++;
			}
			dataTime = dataTime + System.nanoTime() - startTime;

			startTime = System.nanoTime();
			rater.rate(newSubject, data);
			rater.rate(threshold, data);
			ratingTime = ratingTime + System.nanoTime() - startTime;

			startTime = System.nanoTime();
			//if(sortedK.size() > K){
			this.insertElement(newSubject);
			//}
			//else
			//	sortedK.add(newSubject);
			sortTime = sortTime + System.nanoTime() - startTime;

			// Sorts the top k values
			/*Collections.sort(sortedK, new MyTopKCompareValues());
			 
			 if (sortedK.size() > K) {
			 TopKElement last = (TopKElement) sortedK
			 .get(sortedK.size() - 1);
			 topKlist.remove(last);
			 sortedK.remove(last);
			 }
			 */
			startTime = System.nanoTime();
			end = sortedK.size() >= K && testTopK(threshold);
			checkEndTime = checkEndTime + System.nanoTime() - startTime;
		}

		//If we reached the end,
		startTime = System.nanoTime();
		if (data[i].advance() == -1) {
			//mark the finished datasearcher
			finished[i] = true;
			// check, if there are some live datasearcher
			end = checkEnd();
		}
		dataTime = dataTime + System.nanoTime() - startTime;

	}

	/**
	 * Initializes the threshold by first values in all columns.
	 * @param threshold - the threshold to be initialized 
	 */
	private void initThreshold(TopKElement threshold) {

		for (int j = 0; j < data.length; j++) {
			if (!data[j].hasNext()) {
				finished[j] = true;
				continue;
			}
			Object object = data[j].getField(2);
			threshold.setRating(j, object, data[j]);
		}
	}

	/**
	 * Finds the top k elements in selected datasearchers using the threshold algorithm.
	 * 
	 * @return ArrayList of top k elements
	 */
	public ArrayList runThresholdAlgorithm() {
		//		 We are starting, so we initialize threshold
		if (threshold == null) {
			threshold = new TopKElement("threshold", -1, data.length);
			initThreshold(threshold);
		}

		while (end != true) {
			long startTime = System.nanoTime();
			int i = finder.findColumn(this);
			bcfTime = bcfTime + System.nanoTime() - startTime;
			if (i == -1) {
				end = true;
				return createArrayList();
			}
			if (finished[i] == true)
				continue;
			else if (!data[i].hasNext()) {
				finished[i] = true;
				end = checkEnd();
				continue;
			}
			startTime = System.nanoTime();
			rate(threshold, i);
			rateTime = rateTime + System.nanoTime() - startTime;
			step++;
			if (maxStep != -1 && maxStep >= step)
				break;
		}
		return createArrayList();
	}

	/**
	 * Constuctor of algorithm.
	 * It gets all the algortihm needs for function - datasearchers,  rater, 
	 * columnfinder, prefix of data and the number of elements to return.
	 * 
	 * @param data
	 *            DataSearcher[]
	 * @param rater
	 *            Rater
	 * @param finder BestColumnFinder
	 *            
	 * @param prefix String
	 *            
	 * @param K int
	 *            
	 */
	public ThresholdAlgorithm(DataSearcher[] data, Rater rater,
			BestColumnFinder finder, String prefix, int K) {
		super(data, rater, finder, prefix, K);
		sortedK = new ArrayList<TopKElement>();
	}

	/**
	 * Perform one step of algorithm.
	 * 
	 * @return the number of steps already performed.
	 */
	public int step() {
		if (threshold == null) {
			threshold = new TopKElement("threshold", -1, data.length);
			initThreshold(threshold);
		}
		if (end)
			return -1;
		actColumn = finder.findColumn(this);
		if (actColumn == -1) {
			end = true;
			return -1;
		}
		rate(threshold, actColumn);

		actColumn++;
		// TODO Auto-generated method stub
		return actColumn - 1;
	}

}
